package algorithm.tanxin;

import java.util.*;

public class LowestLexicography {

    public static String lowestString1(String[] strs){
        if(strs == null || strs.length == 0)
            return "";
        HashSet<Integer> use = new HashSet<>();
        String path = "";
        ArrayList<String> all = new ArrayList<>();
        process(strs, use, path, all);
        String lowest = all.get(0);
        for (int i = 1; i < all.size(); i++) {
            if(lowest.compareTo(all.get(i)) > 0){
                lowest = all.get(i);
            }
        }
        return lowest;
    }

    public static void process(String[] strs, HashSet use, String path, ArrayList<String> all){
        if(use.size() == strs.length){
            all.add(path);
            return;
        }
        for (int i = 0; i < strs.length; i++) {
            if(!use.contains(i)){
                use.add(i);
                process(strs, use, path + strs[i], all);
                use.remove(i);
            }
        }
    }



    public static String lowestString2(String[] strs){
        if(strs == null || strs.length == 0)
            return "";
        Arrays.sort(strs, new Comparator<String>() {
            @Override
            public int compare(String o1, String o2) {
                return (o1 + o2).compareTo(o2 + o1);
            }
        });
        String res = "";
        for (int i = 0; i < strs.length; i++) {
            res += strs[i];
        }
        return res;

    }
    // for test
    public static String generateRandomString(int strLen) {
        char[] ans = new char[(int)(Math.random()*strLen + 1)];
        for (int i = 0; i < ans.length; i++) {
            ans[i] = (char)(Math.random()*5 + 'a');
        }
        return new String(ans);
    }

    public static String[] generateRandomStringArray(int arrLen, int strLen) {
        String[] strings = new String[(int)(Math.random()*arrLen) + 1];
        for (int i = 0; i < strings.length; i++) {
            strings[i] = generateRandomString(strLen);
        }
        return strings;
    }

    public static String[] copyStringArray(String[] arr) {
        String[] ans = new String[arr.length];
        for (int i = 0; i < ans.length; i++) {
            ans[i] = String.valueOf(arr[i]);
        }
        return ans;
    }


    public static void main(String[] args) {
        int arrLen = 6;
        int strLen = 5;
        int testTimes = 100000;
        for (int i = 0; i < testTimes; i++) {
            String[] arr1 = generateRandomStringArray(arrLen, strLen);
            String[] arr2 = copyStringArray(arr1);
            if (!lowestString1(arr1).equals(lowestString2(arr2))) {
                System.out.println("Oops!");
            }
        }
        System.out.println("finish!");
    }
}
